数据结构 |
您所在的位置:网站首页 › 简单图 多重图 › 数据结构 |
一、图的定义
图中不能一个顶点也没有,图的顶点集V一定非空,但边集E可以为空,此时图中只有顶点而没有边。 二、图的基本概念和术语 1、有向图一个图G若满足:①不存在重复边;②不存在顶点到自身的边,则称图G 为简单图。 4、多重图若图G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则G为多重图。多重图的定义和简单图是相对的。 5、完全图(也称简单完全图)注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。 8、强连通图、强连通分量在有向图中,若从顶点v到顶点w和从顶点w到项点v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量,图G 的强连通分量如下图所示。 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含有n − 1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。 在非连通图中,连通分量的生成树构成了非连通图的生成森林。图G2的一个生成树如下图所示。 在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值。这种边上带有权值的图称为带权图,也称网。 12、稠密图、稀疏图边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图G满足∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V|∣E∣ |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |